/*
MIT License

Copyright (c) 2021 МГТУ им. Н.Э. Баумана, кафедра ИУ-6, Михаил Фетисов,

https://bmstu.codes/lsx/simodo/loom
*/

#include "simodo/interpret/builtins/hosts/fuze/ParsingTableBuilder_SLR.h"

#include "simodo/inout/convert/functions.h"
#include "simodo/inout/format/fmt.h"

#include <algorithm>
#include <cassert>

namespace simodo::interpret::builtins
{
    // По идее - этот вариант должен быть правильной реализацией SLR, т.к.
    // просто поправлена неточность старого алгоритма.
    #define SLR_IMPROVED_1


    void ParsingTableBuilder_SLR::fillStateTable()
    {
        parser::FsmState_t state;
        state.emplace_back(parser::FsmStatePosition(0,0));
        _g.states.emplace_back(state);

        fillStateInfo(0);

        _g.build_method = parser::TableBuildMethod::SLR;
    }

    void ParsingTableBuilder_SLR::fillStateInfo(size_t state_no)
    {
        // Пример грамматики для дальнейшего пояснения:
        // E' = E EOF               // правило 0 (создаётся искусственно)
        // E = E "+" T | T          // правила 1 и 2
        // T = T "*" F | F          // правила 3 и 4
        // F = "(" E ")" | WORD     // правила 5 и 6

        // Функция вызывается, когда уже создано состояние для первой основной позиции
        // Нужно добавить остальные основные позиции, согласно следующему критерию:
        // Состояние НКА соответствует одинаковым позициям правил.
        // Одинаковость позиций определяется тем, что все основные позиции состояния
        // находятся после одного и того же нетерминала
        // Например, если текущей позицией является начало последнего символа в шаблоне первого
        // правила (E = E "+" .T), то находим все замыкания для текущей позиции.
        // В замыкания (closure) попадают все правила, в которых есть начало символа
        // текущей позиции (pos) с учётом рекурсивного нисходящего разворачивания правил.
        // Другими словами, мы должны учесть, какие символы грамматики (терминалы и нетерминалы)
        // могут встретиться на данной позиции, что определяется раскрытием текущего символа
        // (если он нетерминал)
        // Например, если текущей позицией является начало последнего символа в шаблоне первого
        // правила (E = E "+" .T), то замыканиями являются следующие позиции:
        // E = .T
        // T = .T "*" F
        // T = .F
        // F = ."(" E ")"
        // F = .WORD

        /// \attention Код данного метода (как и всего данного класса) выполняет активную модификацию
        /// структур грамматики, заданной в параметре _g. Поэтому, крайне не желательно создавать
        /// ссылки на члены класса _g. Массивы могут реаллокироваться. Будьте осторожны.

        assert(state_no < _g.states.size());
        size_t position_initial_count = _g.states[state_no].size(); // размер массива в цикле не является инвариантом (мы его меняем)

        for(size_t i=0; i < position_initial_count; ++i)
        {
            // Точно известно, что основные позиции состояния добавляются в начало
            if (!_g.states[state_no][i].is_main)
                break;

            size_t rno = _g.states[state_no][i].rule_no;
            size_t pos = _g.states[state_no][i].position;

            assert(rno < _g.rules.size());
            const parser::GrammarRule & rule = _g.rules[rno];   // Текущее правило

            // Находим замыкания и добавляем в заданное состояние как не основные позиции
            if (pos < rule.pattern.size())
                fillPreClosure(state_no, rule.pattern[pos]);
        }

        // Текущее состояние создано, готовим следующие состояния для основных правил
        // Проходим по всем позициям нашего состояния и для каждого перехода
        // создаем следующее состояние. Переходы для одинаковых символов грамматики объединяем,
        // создавая в новом состоянии соотв-щие основные позиции. Проставляем значение next для позиций

        for(size_t i_pos_in_state=0; i_pos_in_state < _g.states[state_no].size(); ++i_pos_in_state)
        {
            size_t current_rno = _g.states[state_no][i_pos_in_state].rule_no;
            size_t current_pos = _g.states[state_no][i_pos_in_state].position;

            assert(current_rno < _g.rules.size());
            const parser::GrammarRule & current_rule = _g.rules[current_rno];

            // Важно убедиться, что есть куда переходить
            if (current_pos == current_rule.pattern.size())
                continue;
            // и эта позиция не использована ранее в этом же цикле (не установлено состояние перехода)
            if (_g.states[state_no][i_pos_in_state].next_state_no > 0)
                continue;

            assert(current_pos < current_rule.pattern.size());
            const inout::Lexeme & current_symbol = current_rule.pattern[current_pos];

            // Для символа конца не создаётся новых состояний
            if (current_symbol.type() == inout::LexemeType::Empty )
                continue;

            // Номер нового состояния будет отличаться от 0
            uint16_t new_state_no = 0;

            // Важно отметить, что основные состояния (FsmStatePosition::is_main == true) уникальны,
            // в то время, как не основные являются сведёнными под совпадающий входной символ
            // и не являются уникальными (см. fillPreClosure)

            // Убеждаемся, что нужного основного состояния ещё нет
            uint16_t find_state = findMainPosition(current_rno, current_pos+1);
            uint16_t next_state_no;
            if (find_state == 0) // (совпадение с нулевым состоянием невозможно, т.к. оно создаётся искусственно)
            {
                // Точного совпадения не нашли
                // Создаем следующее состояние и нашу следующую основную позицию
                next_state_no = static_cast<uint16_t>(_g.states.size());
                _g.states[state_no][i_pos_in_state].next_state_no = new_state_no = next_state_no;

                parser::FsmState_t new_state;
                new_state.emplace_back(current_rno, current_pos+1, true, 0);
                _g.states.emplace_back(new_state);
            }
            else
            {
                next_state_no = find_state;
                _g.states[state_no][i_pos_in_state].next_state_no = find_state;
            }

            // Находим позицию с тем же переходным символом
            for(size_t i_pos_add=i_pos_in_state+1; i_pos_add < _g.states[state_no].size(); ++i_pos_add)
            {
                size_t add_rno = _g.states[state_no][i_pos_add].rule_no;
                size_t add_pos = _g.states[state_no][i_pos_add].position;

                assert(add_rno < _g.rules.size());
                const parser::GrammarRule & add_rule = _g.rules[add_rno];
    #ifdef SLR_IMPROVED_1
                // По идее - этот вариант должен быть правильной реализацией SLR, т.к.
                // просто поправлена неточность старого алгоритма.
                if (add_pos < add_rule.pattern.size())
                    if (current_symbol == add_rule.pattern[add_pos])
                    {
                        // Проверяем, что такой основной позиции ещё нет
                        bool found = false;
                        auto it = _g.states[next_state_no].begin();
                        for(; it != _g.states[next_state_no].end() && it->is_main; ++it)
                            if (it->rule_no == add_rno)
                            {
                                found = true;
                                break;
                            }
                        // Добавляем основную позицию
                        _g.states[state_no][i_pos_add].next_state_no = next_state_no;
                        if (!found)
                        {
                            // Позиция добавляется либо после последней основной, либо в конец списка, если неосновных нет
                            _g.states[next_state_no].emplace(it, add_rno,add_pos+1,true,0);
                            new_state_no = next_state_no;
                        }
                        _g.states[state_no][i_pos_add].next_state_no = next_state_no;
                    }
    #else
                if (add_pos < add_rule.pattern.size())
                    if (current_symbol == add_rule.pattern[add_pos])
                    {
                        _g.states[state_no][i_pos_add].next_state_no = next_state_no;

                        if (find_state == 0)
                        {
                            // Добавляем похожую позицию как основную для нового состояния
                            _g.states[next_state_no].emplace_back(add_rno,add_pos+1,true,0);
                        }
                        else if (add_pos == add_rule.pattern.size()-1)
                        {
                            // Данный блок кода добавлен исключительно для того,
                            // чтобы выявлять неоднозначности грамматики типа R-R,
                            // которые в противном случае остаются непроявленными.
                            // Кроме того, дерево переходов состояния становиться согласованным
                            // и полным, а ошибку можно увидеть визуально.
                            // Сами ошибки выявляются чуть позже
                            // (см. GrammarBuilder_SLR::fillParseTable и GrammarBuilder_SLR::insertValue)
                            size_t i = 0;
                            for(; i < _g.states[next_state_no].size(); ++i)
                                if (_g.states[next_state_no][i].rule_no == add_rno)
                                    break;

                            if (i == _g.states[next_state_no].size())
                                _g.states[next_state_no].emplace_back(add_rno,add_pos+1,true,0);
                        }
                    }
    #endif
            }
            // Вызываем себя рекурсивно, чтобы заполнить созданное состояние по аналогии
            if (new_state_no != 0)
                fillStateInfo(new_state_no);
        }
    }

    uint16_t ParsingTableBuilder_SLR::findMainPosition(size_t rno, size_t pos) const
    {
        for(size_t it_state=0; it_state < _g.states.size(); ++it_state)
        {
            parser::FsmState_t & state = _g.states[it_state];

            for(const parser::FsmStatePosition & p : state)
            {
                // Проверяем только основные позиции, и они всегда в начале
                if (!p.is_main)
                    break;

                if (rno == p.rule_no && pos == p.position)
                    return static_cast<uint16_t>(it_state);
            }
        }

        return 0;
    }

    void ParsingTableBuilder_SLR::fillPreClosure(size_t state_no, const inout::Lexeme &lex) const
    {
        if (lex.type() != inout::LexemeType::Compound)
            return;

        assert(state_no < _g.states.size());

        auto range = _production_index.equal_range(lex.lexeme());

        // Просматриваем продукции заданного символа
        for(auto &it=range.first; it != range.second; ++it)
        {
            size_t                      rno = it->second;
            const parser::GrammarRule & r   = _g.rules[rno];

            size_t i = 0;
            for(; i < _g.states[state_no].size(); ++i)
                if (_g.states[state_no][i].rule_no == rno && _g.states[state_no][i].position == 0)
                    break;

            if (i == _g.states[state_no].size())
            {
                _g.states[state_no].emplace_back(rno, 0, false, 0);
                fillPreClosure(state_no, r.pattern[0]);
            }
        }
    }

    bool ParsingTableBuilder_SLR::fillParseTable()
    {
        bool success = true;

        for(size_t i_state=0; i_state < _g.states.size(); ++i_state)
        {
            const parser::FsmState_t &state = _g.states.at(i_state);

            // Сдвиги имеют больший приоритет (правоассоциативная грамматика)
            for(const parser::FsmStatePosition &p : state)
                if (const parser::GrammarRule & r = _g.rules.at(p.rule_no); p.position < r.pattern.size())
                {
                    const inout::Lexeme & s = r.pattern.at(p.position);

                    if (p.next_state_no == 0)    // 0 не в последней позиции означает завершение
                    {
                        assert(s.type() == inout::LexemeType::Empty);

                        // Принятие (acceptance)
                        if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Acceptance,0)))
                            success = false;
                    }
                    else
                        // p.next != 0 означает наличие перехода в соотв-щее состояние НКА
                        // Сдвиг (shift)
                        if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Shift,static_cast<size_t>(p.next_state_no))))
                            success = false;

                    if (_need_to_break)
                        return false;
                }

            // Свёртки обрабатываем позже, чтобы при конфликтах принимать сдвиги
            // Правила по умолчанию правоассоциативные
            // (свёртки не будут записываться в таблицу, если соотв. позиция занята; кроме правил, помеченных как левоассациативные)
            for(const parser::FsmStatePosition &p : state)
            {
                if (!p.is_main)    // В свёртке могут участвовать только основные позиции, которые находятся всегда в начале списка
                    break;

                if (p.rule_no == 0 || p.next_state_no != 0)
                    continue;

                const parser::GrammarRule &r = _g.rules.at(p.rule_no);

                assert(p.position == r.pattern.size());

                // Свёртка (reduce)
                auto it_reduce_symbols = _reduce_symbol_set.find(r.production);

                if (it_reduce_symbols == _reduce_symbol_set.end())
                {
                    std::vector<inout::Lexeme> reduce_symbols;
                    reduce_symbols.reserve(_g.columns.size()-_g.first_compound_index+1);
                    std::set<size_t> rule_set;

                    fillReduceSymbolsUp(reduce_symbols, rule_set, p.rule_no);

                    auto [it, ok] = _reduce_symbol_set.insert({r.production, {}});

                    assert(ok);
                    it->second.swap(reduce_symbols);

                    it_reduce_symbols = it;
                }

                for(const inout::Lexeme & s : it_reduce_symbols->second)
                    if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Reduce,p.rule_no)))
                        success = false;

                if (_need_to_break)
                    return false;
            }
        }

        return success;
    }

    void ParsingTableBuilder_SLR::fillReduceSymbolsUp(std::vector<inout::Lexeme> & reduce_symbols, std::set<size_t> & rule_set, size_t rule_no)
    {
        const size_t RULE_NUMBER_PACK_BOUNDARY = 10000;

        assert(rule_no < _g.rules.size());
        const std::u16string & production = _g.rules[rule_no].production;

        auto range = _pattern_index.equal_range(production);

        for(auto &it=range.first; it != range.second; ++it) {
            assert(it->second < _g.rules.size());
            size_t next_rule_no = it->second;

            if (rule_set.find(rule_no+RULE_NUMBER_PACK_BOUNDARY*next_rule_no) != rule_set.end())
                continue;

            rule_set.emplace(rule_no+RULE_NUMBER_PACK_BOUNDARY*next_rule_no);

            const parser::GrammarRule & r = _g.rules[next_rule_no];

            for(size_t i_pos=0; i_pos < r.pattern.size(); ++i_pos) {
                const inout::Lexeme & s = r.pattern[i_pos];

                if (s.lexeme() != production)
                    continue;

                // Искомый символ найден!

                // Проверяем позицию в правиле
                if (i_pos == r.pattern.size()-1) {
                    // Последний в шаблоне. Если продукция отличается от искомого, то рекурсивно заполняем по продукции
                    if (r.production != s.lexeme())
                        fillReduceSymbolsUp(reduce_symbols, rule_set, next_rule_no);
                }
                else {
                    const inout::Lexeme & next_symbol = r.pattern[i_pos+1];

                    if (next_symbol.type() == inout::LexemeType::Compound) {
                        std::set<inout::Lexeme> processed;
                        fillReduceSymbolsDown(reduce_symbols, next_symbol.lexeme(), processed);
                    }
                    else if (find(reduce_symbols.begin(), reduce_symbols.end(), next_symbol) == reduce_symbols.end())
                        reduce_symbols.push_back(next_symbol);
                }
            }
        }
    }

    void ParsingTableBuilder_SLR::fillReduceSymbolsDown(std::vector<inout::Lexeme> & reduce_symbols, const std::u16string & production, std::set<inout::Lexeme> & processed)
    {
        auto range = _production_index.equal_range(production);

        // Просматриваем продукции заданного символа
        for(auto & it=range.first; it != range.second; ++it) {
            assert(it->second < _g.rules.size());
            const parser::GrammarRule & r = _g.rules[it->second];

            assert(!r.pattern.empty());
            const inout::Lexeme & s = r.pattern.at(0);

            if (s.type() == inout::LexemeType::Compound) {
                if (s.lexeme() != production)
                    if (processed.end() == processed.find(s)) {
                        processed.insert(s);
                        fillReduceSymbolsDown(reduce_symbols, s.lexeme(), processed);
                    }
            }
            else if (find(reduce_symbols.begin(), reduce_symbols.end(), s) == reduce_symbols.end())
                reduce_symbols.push_back(s);
        }
    }

    bool ParsingTableBuilder_SLR::insertValue(size_t line, size_t column, parser::Fsm_value_t value)
    {
        if (!_g.findFsmValue(line,column))
        {
            // Заданный вариант обработки отсутствует в таблице разбора - просто добавляем
            _g.parse_table.emplace(_g.packFsmKey(line,column),value);
            return true;
        }

        parser::Fsm_value_t exist_value = _g.getFsmValue(line,column);

        parser::FsmActionType exist_action = _g.unpackFsmAction(exist_value);
        parser::FsmActionType new_action   = _g.unpackFsmAction(value);

        // Если вариант обработки в таблице совпадает с заданным - всё ОК
        if (exist_action == new_action && exist_value == value)
            return true;

        // Вариант обработки существует в таблице разбора и он отличается от нашего - нужно принять решение какой из них использовать

        const inout::Lexeme & s = _g.columns.at(column);

        size_t exist_location = _g.unpackFsmLocation(exist_value);
        size_t new_location   = _g.unpackFsmLocation(value);

        std::string sout = inout::fmt("%1'. Состояние %2, символ %3 (#%4). Конфликтуют %5%6 и %7%8. ")
                            .arg(_grammar_name)
                            .arg(line)
                            .arg(inout::getLexemeMnemonic(s))
                            .arg(column)
                            .arg(parser::getFsmActionChar(exist_action))
                            .arg(exist_location)
                            .arg(parser::getFsmActionChar(new_action))
                            .arg(new_location);

        const inout::Token & t = (new_action == parser::FsmActionType::Shift)
                ? _rules[1].pattern[0]
                : _rules[new_location].pattern[_rules[new_location].pattern.size()-1];

        if (exist_action == parser::FsmActionType::Shift && new_action == parser::FsmActionType::Reduce)
        {
            assert(new_location < _g.rules.size());
            assert(new_location < _rules.size());
            if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::RightAssociative)
            {
                sout += inout::fmt("Принят %1%2.")
                            .arg(parser::getFsmActionChar(exist_action))
                            .arg(exist_location);
            }
            else
            {
                _g.parse_table.at(_g.packFsmKey(line,column)) = value;
                sout += inout::fmt("Принят %1%2.")
                            .arg(parser::getFsmActionChar(new_action))
                            .arg(new_location);
            }

            if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::Undefined)
                _m.reportError( t.makeLocation(files()), 
                                inout::fmt("Неоднозначность грамматики '%1").arg(sout));

            return true;
        }

        if (_number_of_collisions == COLLISIONS_LIMIT) {
            _m.reportError( t.makeLocation(files()),
                            inout::fmt("Количество коллизий превысило предел (%1), работа прервана")
                            .arg(COLLISIONS_LIMIT));
            _need_to_break = true;
            return false;
        }

        _m.reportError( t.makeLocation(files()), 
                        inout::fmt("Критическая неоднозначность грамматики '%1").arg(sout));

        _number_of_collisions++;

        return !_strict_rule_consistency;
    }

}